package code20210917;

public class C912 {

	public static void main(String[] args) {
		int[] nums = {1,5,2,8,3,4};
		C912 c = new C912();
		c.quickSort(nums,0,nums.length-1);
		for (int i : nums) {
			System.out.print(i+" ");
		}
	}
	public int[] quickSort(int[] arr,int left,int right) {
		if(left<right) {
			int partitionIndex = partition(arr,left,right);
			quickSort(arr,left,partitionIndex-1);
			quickSort(arr,partitionIndex+1,right);
		}
		return arr;
	}
	public int partition(int[] arr,int left,int right) {
		int pivot = left;
		int index = pivot + 1;
		for(int i=index;i<=right;i++) {
			if(arr[i]<arr[pivot]) {
				swap(arr,i,index++);
			}
		}
		swap(arr,pivot,index-1);
		return index-1;
	}
	public void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}


}
